package com.chj.leetcode.tijie450to500;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Code460_LFUCache2 {
	class LRUCache {

		int capacity;
		Map<Integer, Integer> map;
		Deque<Integer> list;

		public LRUCache(int capacity) {
			this.capacity = capacity;
			this.map = new HashMap<>();
			this.list = new ArrayDeque<Integer>();
		}

		public int get(int key) {
			Integer v = map.get(key);
			if (v != null) {
				list.remove(key);
				list.addLast(key);
				return v;
			}
			return -1;
		}

		public void put(int key, int value) {
			Integer v = map.get(key);
			if (v != null) {
				list.remove(key);
				list.addLast(key);
				map.put(key, value);
				return;
			}

			// 队列未满，添加到尾部
			if (list.size() < capacity) {
				list.addLast(key);
				map.put(key, value);
			} else {
				// 队列已满，移除队首
				Integer firstKey = list.removeFirst();
				map.remove(firstKey);
				list.addLast(key);
				map.put(key, value);
			}
		}
	}
//	作者：icecrea
//	链接：https://leetcode-cn.com/problems/lru-cache/solution/san-chong-fang-fa-dai-ni-shou-si-lrusuan-fa-javaba/
//	来源：力扣（LeetCode）
//	著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
